/* Author: Marco Tezzele 
 * Date: 19 August 2011
 */

/* Algoritmo Dijkstra per i cammini minimi in grafi pesati. */

/* Codici d'errore:
 * 0 = esecuzione terminata correttamente;
 * 1 = errore nell'apertura di un file;
 */

#include <stdio.h>

#define N_MAX   4 /* Numero massimo di nodi */
#define INT_MAX   100 /* Intero massimo per inizializzare d () */
#define X   0 /* Nodo di partenza */
#define Y   3 /* Nodo di arrivo */

int lunghezza_cammino(int, int []); /* Calcola la lunghezza del minimo cammino da X 
				     * a un nodo i (primo argomento), dando il vettore 
				     * u (secondo argomento) */

int weightDijkstra(int argc, char **argv) {

  int i, j, k, m;
  int length; // lunghezza cammino
  int n=N_MAX; // numero di nodi
  float G[N_MAX][N_MAX]; // matrice dei pesi (costi divisibili) 
  float T[N_MAX][N_MAX]; // matrice dei tempi
  float d[N_MAX]; // vettore delle distanze
  int u[N_MAX]; // vettore contenente i percorsi minimi
  int v[N_MAX]; // vettore booleano che serve a marcare i nodi visitati
  int p[N_MAX]; // vettore contenente il percorso minimo al contrario


  /* Controllo se i file vengono aperti correttamente. */
  FILE * fp1 = fopen("weights.txt", "r");
  FILE * fp2 = fopen("times.txt", "r");
  if( fp1 == NULL || fp2 == NULL ) {
    printf("C'e' stato un errore nell'apertura di un file\n");
    return 1;
  } 

  /* Legge i valori da file */
  for(i=0; i<n; ++i) {
    for(j=0; j<n; ++j) {
      fscanf(fp1, "%f", &G[i][j]);
      fscanf(fp2, "%f", &T[i][j]);
    }
  }
  
  fclose(fp1);
  fclose(fp2);

  /* Inizializzo il vettore delle distanze con una distanza massima non 
   * raggiungibile e il vettore dei nodi visitati. */
  for(i=0; i<n; ++i) {
    d[i] = INT_MAX; 
    v[i] = 0;
  }
  
  /* Fisso la prima distanza uguale a zero visto che parto dal vertice in 
   * questione e fisso u del primo nodo uguale a -1 per capire che parto da
   * questo nodo. */
  d[X] = 0;
  u[X] = -1;

  for(;;) {

    /* Cerca il nodo con distanza minima tra quelli non ancora visitati. */
    for(m=INT_MAX, i=0; i<n; ++i) {
      if (!v[i] && d[i] <= m) {
	m = d[j = i];
      }
    }
 
    /* Nodo visitato */
    v[j] = 1;

    /* Quando raggiungo il vertice d'arrivo o arrivo al nodo piu' lontano
     * raggiungibile (Y in questo caso irraggiungibile) mi fermo */
    if (j == Y || m == INT_MAX) 
      break;

    /* Sono al nodo j ora, voglio sapere quanto e' lungo il cammino minimo fino a j */
    length = lunghezza_cammino(j, u);
    //printf("siamo in %d e il cammino minimo e' lungo %d\n", j, length);

    /* Aggiorno la distanza per raggiungere l'i-esimo nodo in base al
     * seguente principio: sono al nodo j, per tutti i nodi i raggiungibili 
     * da j se il costo per raggiungere direttamente i (la distanza da x) e'
     * maggiore del costo del percorso che passa per j (tenendo conto che il costo 
     * del prossimo arco va diviso per i nodi visitati ma non il costo in tempo) 
     * allora forzo il passaggio per j con u[i]=j e assegno la nuova distanza. */
    for(i=0; i<n; ++i) {
      if (G[j][i] && d[i] > d[j] + T[j][i] + G[j][i]/(length+1) ) {
	d[i] = d[j] + T[j][i] + G[j][i]/(length+1);
	u[i] = j;
      }
    }

  }

  /* Memorizziamo l'effettivo percorso minimo ricostruendo all'indietro u */
  j=0;
  p[j] = u[n-1];
  while(p[j] > -1) {
    p[j+1] = u[p[j]];
    ++j;
  }

  /* Stampo la distanza di tutti i nodi da X */
  printf("d = ");
  for(i=0; i<n; ++i)
    printf("%f ", d[i]);
  printf("\n");

  /* Stampo il vettore dei percorsi minimi partendo da X */
  printf("u = ");
  for(i=0; i<n; ++i)
    printf("%d ", u[i]);
  printf("\n");

  length = lunghezza_cammino(Y, u);

  printf("Il percorso minimo per andare da %d a %d e' il seguente:\n", X, Y);
  for(i=j-1; i>=0; --i)
    printf("%d -> ", p[i]);
  printf("%d\n", Y);
  printf("ha una lunghezza pari a: %d \ned un costo pari a: %f\n", length, d[n-1]);

  return 0;
}

int lunghezza_cammino(int j, int u[]) {
  int i=0;
  int p;

  p = u[j];
  while(p > -1) {
    p = u[p];
    ++i;
  }

  return i;
}
